#include <bits/stdc++.h>
using namespace std;

#define zerol

using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout  << #x << " -> "; err(x); } while (0)
void err() { cout << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#else
#define dbg(...)
#endif


//--------------------------------------------------------------------------------------------

struct ios {
    inline char read(){
        static const int IN_LEN=1<<18|1;
        static char buf[IN_LEN],*s,*t;
        return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;
    }

    template <typename _Tp> inline ios & operator >> (_Tp&x){
        static char c11,boo;
        for(c11=read(),boo=0;!isdigit(c11);c11=read()){
            if(c11==-1)return *this;
            boo|=c11=='-';
        }
        for(x=0;isdigit(c11);c11=read())x=x*10+(c11^'0');
        boo&&(x=-x);
        return *this;
    }
} io;

const int MAXN = 3e5+5;


LL s[MAXN];
inline bool check(int l, int r, int maxv) {
    LL sum = s[r];
    if (l > 0) sum -= s[l-1];
    if (sum % 2) --sum;
    return sum-maxv < maxv;
}

pair<int, int> pos[MAXN];
int n;
int a[MAXN];

inline int findr(int lp, int rp, int nowp, int nowv) {
    if (!check(lp, nowp, nowv)) return -1;
    if (check(lp, rp, nowv)) return rp;
    int l = nowp, r = rp, m;
    while (l < r-1) {
        m = (l+r) >> 1;
        if (check(lp, m, nowv)) l = m;
        else r = m;
    }
    return l;
}

int main(int argc, char const *argv[])
{
    int t;
    // scanf("%d", &t);
    io >> t;
    for (int kk=0; kk<t; ++kk) {
        io >> n;
        for (int i=0; i<n; ++i) {
            io >> a[i];
            pos[i] = make_pair(a[i], i);
        }
        s[0] = 0;
        for (int i=1; i<n; ++i)
            s[i] = s[i-1] + a[i];
        sort(pos, pos + n);
        set<int> S; S.clear();
        set<int>::iterator it[2];

        LL ans = 0;
        int lp, rp;
        for (int i=n-1; i>=0; --i) {
            int nowp = pos[i].second,
            nowv = pos[i].first;

            // if (i == n-1 || nowv != a[i+1]) {
            it[0] = S.lower_bound(nowp);
            if (it[0] == S.begin()) {
                lp = 0;
            } else {
                --it[0];
                lp = *it[0] + 1;
            }
            S.insert(nowp);
            it[1] = S.lower_bound(nowp+1);
            
            
            if (it[1] == S.end()) {
                rp = n-1;
            } else {
                rp = *it[1] - 1;
            }
            // }

            

            LL tot = 1LL*(nowp-lp+1) * (rp-nowp+1), tans = 0;

            dbg(lp, rp, nowp, nowv);

            int l = lp, r = findr(l, rp, nowp, nowv);
            while (r == -1) {
                ++l;
                r = findr(l, rp, nowp, nowv);
            }
            for (; l<=nowp; ++l) {
                while (r+1<=rp && !check(l, r+1, nowv)) ++r;
                tans += r-nowp+1;
                dbg(l, nowp, r);
            }

            ans += tot-tans;
        }

        printf("%lld\n", ans);
    }
    return 0;
}

